// https://www.luogu.com.cn/problem/P2871
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
#define MAX_SIZE 10005
#define MAXN 10005

int n, m;
int p[MAXN], v[MAXN];
int f[2][MAX_SIZE];

int main() {
    scanf("%d%d", &m, &n);
    rf(i, n) scanf("%d%d", &p[i], &v[i]);

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            f[i & 1][j] = f[i - 1 & 1][j];
            if (j >= v[i]) f[i & 1][j] = max(f[i & 1][j], f[i & 1][j - v[i]] + p[i]);
        }
    }
    // puts("");
    // rf(i, n) {
    //     for (int j = 0; j <= m; ++j)
    //         printf("%d ", f[i][j]);
    //     puts("");
    // }
    printf("%d", f[n & 1][m]);
}
